﻿//====================================================
//| Downloaded From                                  |
//| Visual C# Kicks - http://www.vcskicks.com/       |
//| License - http://www.vcskicks.com/license.html   |
//====================================================
using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace GenericLibrary.Common
{

    /// <summary>
    /// Priority Queue data structure
    /// </summary>
    public class PriorityQueue1<T>
        where T : IComparable
    {

        protected List<T> storedValues;

        public PriorityQueue1()
        {
            //Initialize the array that will hold the values
            storedValues = new List<T>();

            //Fill the first cell in the array with an empty value
            storedValues.Add(default(T));
        }

        /// <summary>
        /// Gets the number of values stored within the Priority Queue
        /// </summary>
        public virtual int Count
        {
            get { return storedValues.Count - 1; }
        }

        /// <summary>
        /// Returns the value at the head of the Priority Queue without removing it.
        /// </summary>
        public virtual T Peek()
        {
            if (this.Count == 0)
                return default(T); //Priority Queue empty
            else
                return storedValues[1]; //head of the queue
        }

        /// <summary>
        /// Adds a value to the Priority Queue
        /// </summary>
        public virtual void Enqueue(T value)
        {
            //Add the value to the internal array
            storedValues.Add(value);

            //Bubble up to preserve the heap property,
            //starting at the inserted value
            this.BubbleUp(storedValues.Count - 1);
        }

        /// <summary>
        /// Returns the minimum value inside the Priority Queue
        /// </summary>
        public virtual T Dequeue()
        {
            if (this.Count == 0)
                return default(T); //queue is empty
            else
            {
                //The smallest value in the Priority Queue is the first item in the array
                T minValue = this.storedValues[1];

                //If there's more than one item, replace the first item in the array with the last one
                if (this.storedValues.Count > 2)
                {
                    T lastValue = this.storedValues[storedValues.Count - 1];

                    //Move last node to the head
                    this.storedValues.RemoveAt(storedValues.Count - 1);
                    this.storedValues[1] = lastValue;

                    //Bubble down
                    this.BubbleDown(1);
                }
                else
                {
                    //Remove the only value stored in the queue
                    storedValues.RemoveAt(1);
                }

                return minValue;
            }
        }

        /// <summary>
        /// Restores the heap-order property between child and parent values going up towards the head
        /// </summary>
        protected virtual void BubbleUp(int startCell)
        {
            int cell = startCell;

            //Bubble up as long as the parent is greater
            while (this.IsParentBigger(cell))
            {
                //Get values of parent and child
                T parentValue = this.storedValues[cell / 2];
                T childValue = this.storedValues[cell];

                //Swap the values
                this.storedValues[cell / 2] = childValue;
                this.storedValues[cell] = parentValue;

                cell /= 2; //go up parents
            }
        }

        /// <summary>
        /// Restores the heap-order property between child and parent values going down towards the bottom
        /// </summary>
        protected virtual void BubbleDown(int startCell)
        {
            int cell = startCell;

            //Bubble down as long as either child is smaller
            while (this.IsLeftChildSmaller(cell) || this.IsRightChildSmaller(cell))
            {
                int child = this.CompareChild(cell);

                if (child == -1) //Left Child
                {
                    //Swap values
                    T parentValue = storedValues[cell];
                    T leftChildValue = storedValues[2 * cell];

                    storedValues[cell] = leftChildValue;
                    storedValues[2 * cell] = parentValue;

                    cell = 2 * cell; //move down to left child
                }
                else if (child == 1) //Right Child
                {
                    //Swap values
                    T parentValue = storedValues[cell];
                    T rightChildValue = storedValues[2 * cell + 1];

                    storedValues[cell] = rightChildValue;
                    storedValues[2 * cell + 1] = parentValue;

                    cell = 2 * cell + 1; //move down to right child
                }
            }
        }

        /// <summary>
        /// Returns if the value of a parent is greater than its child
        /// </summary>
        protected virtual bool IsParentBigger(int childCell)
        {
            if (childCell == 1)
                return false; //top of heap, no parent
            else
                return storedValues[childCell / 2].CompareTo(storedValues[childCell]) > 0;
            //return storedNodes[childCell / 2].Key > storedNodes[childCell].Key;
        }

        /// <summary>
        /// Returns whether the left child cell is smaller than the parent cell.
        /// Returns false if a left child does not exist.
        /// </summary>
        protected virtual bool IsLeftChildSmaller(int parentCell)
        {
            if (2 * parentCell >= storedValues.Count)
                return false; //out of bounds
            else
                return storedValues[2 * parentCell].CompareTo(storedValues[parentCell]) < 0;
            //return storedNodes[2 * parentCell].Key < storedNodes[parentCell].Key;
        }

        /// <summary>
        /// Returns whether the right child cell is smaller than the parent cell.
        /// Returns false if a right child does not exist.
        /// </summary>
        protected virtual bool IsRightChildSmaller(int parentCell)
        {
            if (2 * parentCell + 1 >= storedValues.Count)
                return false; //out of bounds
            else
                return storedValues[2 * parentCell + 1].CompareTo(storedValues[parentCell]) < 0;
            //return storedNodes[2 * parentCell + 1].Key < storedNodes[parentCell].Key;
        }

        /// <summary>
        /// Compares the children cells of a parent cell. -1 indicates the left child is the smaller of the two,
        /// 1 indicates the right child is the smaller of the two, 0 inidicates that neither child is smaller than the parent.
        /// </summary>
        protected virtual int CompareChild(int parentCell)
        {
            bool leftChildSmaller = this.IsLeftChildSmaller(parentCell);
            bool rightChildSmaller = this.IsRightChildSmaller(parentCell);

            if (leftChildSmaller || rightChildSmaller)
            {
                if (leftChildSmaller && rightChildSmaller)
                {
                    //Figure out which of the two is smaller
                    int leftChild = 2 * parentCell;
                    int rightChild = 2 * parentCell + 1;

                    T leftValue = this.storedValues[leftChild];
                    T rightValue = this.storedValues[rightChild];

                    //Compare the values of the children
                    if (leftValue.CompareTo(rightValue) <= 0)
                        return -1; //left child is smaller
                    else
                        return 1; //right child is smaller
                }
                else if (leftChildSmaller)
                    return -1; //left child is smaller
                else
                    return 1; //right child smaller
            }
            else
                return 0; //both children are bigger or don't exist
        }

    }

    public interface IPriorityQueue
    {

        IEnumerable<IPriorityEntry> Peek { get; }//return all entries that have the minimum priority
        IEnumerable<IPriorityEntry> Dequeue();//dequeue all entries that have the minimum priority
        void Enqueue(IPriorityEntry entry);//if the given entry already existed in the queue,its queueing position will be updated

    }

    public interface IPriorityQueue<T> where T : IPriorityEntry
    {
        IEnumerable<T> Peek { get; }
        IEnumerable<T> Dequeue();
        void Enqueue(T entry);
    }

    public interface IPriorityEntry
    {
        double ComparePriority(IPriorityEntry other);
        void OnDequeue(IPriorityQueue queue);
    }

    //How the Output Timing(priority) to relate with the object states?? 

    //public abstract class DiscreteEventProcess : IPriorityEntry
    //{

    //    protected abstract double CompareTiming(DiscreteEventProcess other);
    //    protected abstract void OnSynchronize(double timeSpan);
    //    protected IEnumerable<DiscreteEventProcess> OnActivate();//Return effective processes,execution of this method should not depend on the context but only the state of the subjective process!!!
    //    protected abstract void OnContextChanged(IEnumerable<DiscreteEventProcess> causativeProcesses);


    //    private static IPriorityQueue<DiscreteEventProcess> _queue;

    //    public static bool Iterate()
    //    {
    //        IEnumerable<DiscreteEventProcess> causativePop = _queue.Dequeue();
    //        if (causativePop != null)
    //        {
    //            Dictionary<DiscreteEventProcess, List<DiscreteEventProcess>> effectivePop = new Dictionary<DiscreteEventProcess, List<DiscreteEventProcess>>();
    //            foreach (DiscreteEventProcess causativeProc in causativePop)
    //            {
    //                foreach (DiscreteEventProcess effectiveProc in causativeProc.OnActivate())
    //                {
    //                    if (!(effectivePop.ContainsKey(effectiveProc)))
    //                    {
    //                        effectivePop[effectiveProc] = new List<DiscreteEventProcess>();
    //                    }
    //                    effectivePop[effectiveProc].Add(causativeProc);
    //                }
    //            }
    //            foreach (DiscreteEventProcess effectiveProc in effectivePop.Keys)
    //            {
    //                IList<DiscreteEventProcess> causativeProc = effectivePop[effectiveProc];
    //                double timeSpan = effectiveProc.CompareTiming(causativeProc[0]);
    //                effectiveProc.OnSynchronize(timeSpan);
    //                effectiveProc.OnContextChanged(causativeProc);
    //                _queue.Enqueue(effectiveProc);
    //            }
    //        }
    //        return _queue.Peek != null;
    //    }

    //}

    //public abstract class DiscreteStateContext<T> where T : DiscreteStateContext<T>
    //{
    //    //this interface ignores identifying of the state;
    //    //This is a immutable type
    //    public interface IDiscreteState
    //    {
    //        /// <summary>
    //        /// Compare the current time of this state with another state
    //        /// </summary>
    //        /// <param name="other"></param>
    //        /// <returns>return the difference between the current time of this state and the other state</returns>
    //        double CompareTiming(IDiscreteState other);

    //        /// <summary>
    //        /// Defines the Transition rule of this state
    //        /// </summary>
    //        /// <param name="timeElapsed">
    //        /// The time span this state has lived to the moment this transition is being invoked.
    //        /// </param>
    //        /// <param name="context">
    //        /// When not null, the transition will be external, stimulated by external inputs or changing of super states;
    //        /// When null, the transition will be internal, self-stimulated due to delayed transaction
    //        /// </param>
    //        /// <param name="subStates">
    //        /// Return all sub-states affected by this transition. These sub-states will be enqueued as per their priority by the framework for updating.  
    //        /// </param>
    //        /// <returns>
    //        /// Return the resulting state of the transition on this state
    //        /// </returns>
    //        IDiscreteState Transition(double timeElapsed, T context, out IEnumerable<IDiscreteState> subStates);

    //        /// <summary>
    //        /// The life span of this state. When the life span expires, internal transition will be invoked on this state by the framework.
    //        /// </summary>
    //        double LifeSpan { get; }
    //    }

    //    private double CompareStateTransitionPriority(IDiscreteState state1, IDiscreteState state2)
    //    {
    //        return state1.CompareTiming(state2) + (state1.LifeSpan - state2.LifeSpan);
    //    }

    //    public delegate void OnStateChange();

    //    //Provide any state query functionalities in the sub-class!

    //    protected abstract double CompareTiming(IDiscreteState state1, IDiscreteState state2);
    //    protected abstract void SetState(IDiscreteState state);

    //    private IPriorityQueue<IDiscreteState> _queue;//Do not put all states into the queue!


    //}

    //还是必须使用输入输出来解除Agent之间的偶合，由Framework来统一管理Agent生命周期（按需实例化Agent，Instantiating object on demand），Agent只与Framework交互，Agent将event发送给Framework，Framework将实例化处理该event的Agent，并将event发送给它，既然由Framework管理Agent实例，要求Agent实现new（），因此表面上是Framework在处理event，在内部Framework将event委托给具体的Agent处理，并管理Agent的状态

    //用输入输出隔离能够避免在对象间交互是必须同步！必须使用输入输出来避免对象间直接交互，直接交互的结果就是需要进行时间同步
    //public abstract class Node
    //{
    //    public enum SimulationState { Synchronizing, Outputing, Synchronized }

    //    public class OutputPriorityComparer : IComparer<Node>
    //    {
    //        public int Compare(Node x, Node y)
    //        {
    //            return x.StateChangeTime.CompareTo(y.StateChangeTime);
    //        }
    //    }

    //    private static Network _network; //把这个在下个继承类内处理,只需对Queue进行时间同步

    //    private double _stateTime, _stateChangeTiming;

    //    protected IEnumerable<Node> ChildNodes { get; }
    //    protected abstract double OnInitialized();
    //    protected abstract double OnParentNodeStateChanged(double timeSpan, Node parentNode); //return updated output timing,current time will hold!
    //    protected abstract double TransitionState();//return next transition timing.

    //    //protected abstract bool StateConverged { get; }//if the node is state-converged, time change will not affect its state any more
    //    //只有Synchronize操作才能改变CurrentTime
    //    protected abstract void OnTimeAdvanced(double timeSpan);
    //    //执行后对象的CurrentTime不能改变,返回受影响的Nodes
    //    protected abstract void OnStateChanged(IEnumerable<Node> contextNodes);//此方法还应包含对状态固定点的调用！

    //    protected abstract void InternalTransition(double timeSpan);
    //    protected abstract void ExternalTransition(IEnumerable<T> contextNodes);
    //    protected double TransitionTiming { get; }

    //    protected abstract double OnTransition(double timeElapsed, IEnumerable<Node> contextNodes);//被Queue调用时contextNodes为null

    //    internal void InternalTransition(double timeElapsed)
    //    {
    //        this._stateTime += timeElapsed;
    //        this._stateChangeTiming = this.OnTransition(timeElapsed, null);
    //    }

    //    internal void ExternalTransition(IList<Node> contextNodes)
    //    {
    //        double timeElapsed = contextNodes[0]._stateTime - this._stateTime;
    //        this._stateTime += timeElapsed;
    //        this._stateChangeTiming = this.OnTransition(timeElapsed, contextNodes);
    //    }

    //    private double StateChangeTime
    //    {
    //        get
    //        {
    //            return this._stateTime + this._stateChangeTiming;
    //        }
    //    }

    //    internal double StateChangeTiming
    //    {
    //        get
    //        {
    //            return this._stateChangeTiming;
    //        }
    //    }

    //    //Synchronization should not affect output time!
    //    //Synchronization将在Node被其他Node访问和系统同步时调用
    //    private void Synchronize(double timeSpan)
    //    {
    //        if (timeSpan < 0)
    //        {
    //            throw new Exception();
    //        }
    //        this.OnTimeAdvanced(timeSpan);
    //        this._stateTime += timeSpan;
    //        this._stateChangeTiming -= timeSpan;
    //    }

    //    private void Output(IEnumerable<Node> contextNodes)
    //    {
    //        this.Synchronize(this._stateChangeTiming);
    //        foreach (Node node in contextNodes)
    //        {
    //            node.Synchronize(this._stateTime - node._stateTime);
    //        }
    //        this._stateChangeTiming = double.PositiveInfinity;
    //        this.OnStateChanged(contextNodes);
    //    }

    //    //在Output之后将被Framework重置为PositiveMax，排除出执行队列
    //    protected double StateChangeTiming
    //    {
    //        get
    //        {
    //            return this._stateChangeTiming;
    //        }
    //        set
    //        {
    //            if (value < 0)
    //            {
    //                throw new Exception();
    //            }
    //            else if (value == double.PositiveInfinity)//输出时间无限远是否意味Converged？
    //            {
    //                _network.Dequeue(this);
    //            }
    //            this._stateChangeTiming = value;
    //            _network.Enqueue(this);
    //        }
    //    }


    //}

    //public abstract class Network : PriorityQueue<Node>
    //{
    //    protected internal abstract IEnumerable<Node> GetContextNodes(Node agent);
    //    protected internal abstract IEnumerable<Node> Nodes { get; }
    //    protected internal abstract IEnumerable<Node> GetDependentNodes(Node node);

    //    private IEnumerable<Node> GetChangingNodes()
    //    {
    //        Node node;
    //        do
    //        {
    //            node = this.Peek;
    //            this.Dequeue(node);
    //            yield return node;
    //        } while (this.EntryComparer.Compare(this.Peek, node) == 0);
    //    }

    //    public void Step()
    //    {
    //        List<Node> changingNodes = new List<Node>(this.GetChangingNodes());
    //        Dictionary<Node, List<Node>> dependentNodes = new Dictionary<Node, List<Node>>();
    //        foreach (Node node in changingNodes)
    //        {
    //            node.InternalTransition(node.StateChangeTiming);
    //            foreach (Node dependentNode in this.GetDependentNodes(node))
    //            {
    //                if (!dependentNodes.ContainsKey(dependentNode))
    //                {
    //                    dependentNodes[dependentNode] = new List<Node>();
    //                }
    //                dependentNodes[dependentNode].Add(node);
    //            }
    //        }
    //        foreach (Node dependentNode in dependentNodes.Keys)
    //        {
    //            dependentNode.ExternalTransition(dependentNodes[dependentNode]);
    //        }


    //    }


    //}

    //public class PriorityQueue<T>
    //{

    //    private List<T> _entryByIndex;
    //    private Dictionary<T, int> _indexByEntry;
    //    private IComparer<T> _priorityComparer;

    //    //参数有效假设

    //    public IComparer<T> EntryComparer
    //    {
    //        get
    //        {
    //            return this._priorityComparer;
    //        }
    //    }

    //    private void SwapEntry(int index1, int index2)
    //    {
    //        T entry = this._entryByIndex[index1];
    //        this._entryByIndex[index1] = this._entryByIndex[index2];
    //        this._entryByIndex[index2] = entry;
    //    }



    //    private int BubbleUp(int index)
    //    {
    //        int parentIndex;
    //        while (true)
    //        {
    //            parentIndex = (index - 1) / 2;
    //            if (parentIndex >= 0 && this._priorityComparer.Compare(this._entryByIndex[index], this._entryByIndex[parentIndex]) > 0)
    //            {
    //                this.SwapEntry(index, parentIndex);
    //                this._indexByEntry[this._entryByIndex[index]] = index;
    //                index = parentIndex;
    //            }
    //            else
    //            {
    //                this._indexByEntry[this._entryByIndex[index]] = index;
    //                return index;
    //            }
    //        }
    //    }

    //    private int BubbleDown(int index)
    //    {
    //        int leftChildIndex, rightChildIndex, childIndex;
    //        while (true)
    //        {
    //            leftChildIndex = index * 2 + 1;
    //            rightChildIndex = leftChildIndex + 1;

    //            if (rightChildIndex < this._entryByIndex.Count && this._priorityComparer.Compare(this._entryByIndex[rightChildIndex], this._entryByIndex[leftChildIndex]) > 0)
    //            {
    //                if (this._priorityComparer.Compare(this._entryByIndex[index], this._entryByIndex[rightChildIndex]) < 0)
    //                {
    //                    this.SwapEntry(index, rightChildIndex);
    //                    this._indexByEntry[this._entryByIndex[index]] = index;
    //                    index = rightChildIndex;
    //                }
    //            }
    //            else if (leftChildIndex < this._entryByIndex.Count)
    //            {
    //                if (this._priorityComparer.Compare(this._entryByIndex[index], this._entryByIndex[leftChildIndex]) < 0)
    //                {
    //                    this.SwapEntry(index, leftChildIndex);
    //                    this._indexByEntry[this._entryByIndex[index]] = index;
    //                    index = leftChildIndex;
    //                }
    //            }
    //            else
    //            {
    //                this._indexByEntry[this._entryByIndex[index]] = index;
    //                return index;
    //            }

    //            if (this._priorityComparer.Compare(this._entryByIndex[index], this._entryByIndex[childIndex]) < 0)
    //            {
    //                this.SwapEntry(index, childIndex);
    //                this._indexByEntry[this._entryByIndex[index]] = index;
    //                index = childIndex;
    //            }
    //            else
    //            {
    //                this._indexByEntry[this._entryByIndex[index]] = index;
    //                return index;
    //            }
    //        }
    //    }

    //    private void Fix(int index)
    //    {



    //        //T entry;
    //        //int i = index;
    //        //while (true)
    //        //{
    //        //    int parentIndex = (i - 1) / 2;
    //        //    if (parentIndex >= 0 && this._priorityComparer.Compare(this._entryByIndex[i], this._entryByIndex[parentIndex]) > 0)
    //        //    {
    //        //        entry = this._entryByIndex[parentIndex];
    //        //        this._entryByIndex[parentIndex] = this._entryByIndex[i];
    //        //        this._entryByIndex[i] = entry;
    //        //        this._indexByEntry[entry] = i;
    //        //        i = parentIndex;
    //        //    }
    //        //    else if (i != index)
    //        //    {
    //        //        this._indexByEntry[this._entryByIndex[i]] = i;
    //        //        return;
    //        //    }
    //        //}

    //        //int leftChildIndex = index * 2 + 1;
    //        //int rightChildIndex = leftChildIndex + 1;



    //        //this._indexByEntry[this._entryByIndex[index]] = index;

    //    }

    //    public void Enqueue(T entry)
    //    {
    //        int index;
    //        if (!this._indexByEntry.TryGetValue(entry, out index))
    //        {
    //            this._entryByIndex.Add(entry);
    //            index = this._entryByIndex.Count - 1;
    //            this._indexByEntry[entry] = index;
    //        }
    //        this.Fix(index);
    //    }

    //    public void Dequeue(T entry)
    //    {
    //        int index;
    //        if (this._indexByEntry.TryGetValue(entry, out index))
    //        {
    //            int lastIndex = this._entryByIndex.Count - 1;
    //            this._entryByIndex[index] = this._entryByIndex[lastIndex];
    //            this._indexByEntry.Remove(this._entryByIndex[lastIndex]);
    //            this._entryByIndex.RemoveAt(lastIndex);
    //            this.Fix(index);
    //        }
    //    }

    //    public T Peek
    //    {
    //        get
    //        {
    //            return this._entryByIndex[0];
    //        }
    //    }

    //    public int Count
    //    {
    //        get
    //        {
    //            return this._entryByIndex.Count;
    //        }
    //    }

    //    public bool Contains(T entry)
    //    {
    //        return this._indexByEntry.ContainsKey(entry);
    //    }

    //    public PriorityQueue(IComparer<T> priorityComparer)
    //    {
    //        this._priorityComparer = priorityComparer;
    //        this._indexByEntry = new Dictionary<T, int>();
    //        this._entryByIndex = new List<T>();
    //    }


    //}



}
